Conventionally, in a computer system, a data entity is electronically stored at and fetched from a particular location in a memory system that is uniquely identified by an address. Irk such an address based system, data are accessed by inputting an address corresponding to the data to the memory system which then utilizes the address information to locate the data for output by the memory system.
A content-addressable memory is a memory system which stores and retrieves data based on its content rather than on an associated address. The memory is viewed as a representation of the information it contains rather than as a consecutive sequence of uniquely identified locations containing unrelated data. Content addressable memories may be used, for example, in set associative caches.
One particular application of a content addressable memory is to recognize a sparsely populated matrix, i.e., a small preselected set of data entities to be recognized from a large number of possible input data entities.
For example, a computer network using a 48-bit address to uniquely identify and address a component on the network can have any one of 2.sup.48 possible different addresses appear on an address bus coupling the components of the network. A node on the network intercoupling, for example, 64 components to the bus, would have to be able to recognize when one of the components is being addressed, i.e., to recognize a set of 64 specific addresses from the 2.sup.48 possible addresses.
A software content addressable memory can be achieved by the use of hashing algorithms which, for example, use software to process an input data entity to determine whether it is of interest. A software model is not desirable in many instances because it is generally slower in operation than a hardware model.
In the existing art, a hardware content addressable memory typically comprises a system of stored table data entries which are to be compared to the content of a data entity input to the memory system. Table entries are stored in a look-up table and are each compared with a data entity input to the memory system. A match signal indicates that the input data entity exists as a table entry in the look-up table.
An example of such a system is one in which a register is provided for each table entry and stores one table entry. Each register is coupled to a comparator. Each comparator is also coupled to a bus on which a data entity is input to the content addressable memory for comparison. The comparator operates to compare data of a particular table entry stored in its corresponding register, with a data entity input to the content addressable memory. If the data of the table entry contained in the register matches the input data entity, the comparator corresponding to the particular register will output a match signal indicating that the input data entity is in the content addressable memory. All of the comparators in the memory system are arranged in parallel to one another relative to the data entity input bus and thus receive the input data entity simultaneously.
Such a system is relatively slow in operation, when used with large input data entities, such as 48-bit data entities, because of the relative time it takes to compare large multiple bit numbers. In addition to being too slow, such systems, in certain applications, also tend to be too cumbersome due to the numerous comparators that may be required.
Thus, a need generally exists for a hardware content addressable memory which can quickly and accurately identify a sparsely populated matrix.